#include <vector>
#include <algorithm>
#include "convex_hull.h"

void quick_hull_step(const std::vector<Point> &points, std::vector<Point> &ans, 
	int left, int right, const std::vector<int> &sub)
{
	if (sub.size() == 0) 
	{
		ans.push_back(points[right]);
		return;
	}

	int farest = sub[0];
	Line line = Line(points[left], points[right]), topline = Line(points[left], points[farest]);
	for (int i = 1; i < sub.size(); i++) 
	{
		if (sub[i] != left && sub[i] != right)
		{
			int dist = closer(line, points[farest], points[sub[i]]);
			if (dist < 0 || (dist == 0 && left_turn(topline.a, topline.b, points[sub[i]])))
			{
				farest = sub[i];
				topline = Line(points[left], points[farest]);
			}
		}
	}

	std::vector<int> lefter, righter;

	for (int i = 0; i < sub.size(); i++) 
	{
		if (left_turn(points[left], points[farest], points[sub[i]]) > 0)
		{
			lefter.push_back(sub[i]);
		}

		if (left_turn(points[farest], points[right], points[sub[i]]) > 0)
		{
			righter.push_back(sub[i]);
		}
	}
	
	quick_hull_step(points, ans, left, farest, lefter);
	quick_hull_step(points, ans, farest, right, righter);
}

void quick_hull(const std::vector<Point> &points, std::vector<Point> &ans)
{
	if (points.size() < 3)
	{
		ans = points;
		return;
	}

	int left = std::min_element(points.begin(), points.end()) - points.begin();
	int right = std::max_element(points.begin(), points.end()) - points.begin();

	std::vector<int> upper, lower;

	for (int i = 0; i < points.size(); i++)
	{
		if (i != left && i != right) 
		{
			int turn = left_turn(points[left], points[right], points[i]);
			if (turn > 0)
			{
				upper.push_back(i);
			}
			if (turn < 0)
			{
				lower.push_back(i);
			}
		}
	}

	quick_hull_step(points, ans, left, right, upper);
	quick_hull_step(points, ans, right, left, lower);

	if (ans.size() == 2 && ans[0] == ans[1]) // equal points
	{
		ans.pop_back();
	}
}
